'''
快速排序：
选择一个基数，将其它数分为左边，右边，和中间（一样）
然后，再对左边和右边的数组进行一样的操作。
原理就是二分法+递归

确定一个中间值，把左边和右边都排序。相当于2分排序。

'''
def quick_sort(nums):
    print("nums=", nums)
    if len(nums) <= 1:
        return nums # 返回的是数组
    pivot = nums[len(nums) // 2]
    print("pivot=", pivot)
    left = [x for x in nums if x < pivot]
    middle = [x for x in nums if x == pivot]
    right = [x for x in nums if x > pivot]
    
    print("left=", left)
    print("middle=", middle)
    print("right=", right)
    
    # 相加后依然是数组
    final = quick_sort(left) + middle + quick_sort(right)
    print("final=", final)
    return final

def sortArray(nums):
    return quick_sort(nums)

def test_sortArray():
    # 测试示例 1
    assert sortArray([5, 2, 3, 1]) == [1, 2, 3, 5], "测试示例 1 失败"
    
    # 测试示例 2
    assert sortArray([5, 1, 1, 2, 0, 0]) == [0, 0, 1, 1, 2, 5], "测试示例 2 失败"
    
    # 测试示例 3: 已经有序的数组
    assert sortArray([1, 2, 3, 4, 5]) == [1, 2, 3, 4, 5], "测试示例 3 失败"
    
    # 测试示例 4: 逆序数组
    assert sortArray([5, 4, 3, 2, 1]) == [1, 2, 3, 4, 5], "测试示例 4 失败"
    
    # 测试示例 5: 包含重复元素的数组
    assert sortArray([4, 2, 2, 8, 3, 3, 1]) == [1, 2, 2, 3, 3, 4, 8], "测试示例 5 失败"
    
    # 测试示例 6: 空数组
    assert sortArray([]) == [], "测试示例 6 失败"
    
    # 测试示例 7: 只有一个元素的数组
    assert sortArray([1]) == [1], "测试示例 7 失败"
    
    print("所有测试用例通过！")

# 运行测试
test_sortArray()